package com.bo.day20240913;


import java.util.*;
/**
 * 将一个多叉树转为一个二叉树,
 * 一个二叉树再转为多叉树
 * 图解：https://cloud.fynote.com/share/d/1HLINP7k
 * @Author: gpb
 * @Date: 2024/9/13 14:59
 * @Description:
 */
public class EncodeNaryTreeToBinaryTree {
    // 提交时不要提交这个类
    public static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };

    // 提交时不要提交这个类
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 只提交这个类即可
    class Codec {

        /**
         * 将一个多叉树转换为一个二叉树
         * 思路：将自己的孩子都挂在左树的右边届上
         * @param root
         * @return
         */
        public TreeNode encode(Node root) {
            if (root == null){
                return null;
            }
            TreeNode head = new TreeNode(root.val);
            head.left = en(root.children);
            return head;
        }

        private TreeNode en (List<Node> children) {
            // 初始化
            TreeNode head = null;
            // 作为右边边节点
            TreeNode cus = null;
            // 遍历孩子节点
            for (Node child : children) {
                // 初始化二叉树节点
                TreeNode t = new TreeNode(child.val);
                // 如果head为空，说明是第一个孩子，直接赋值给head，否则，将当前节点挂到cus的右边界上
                if (head == null) {
                    head = t;
                } else {
                    cus.right = t;
                }
                // 右边界上,继续往下走
                cus = t;
                cus.left = en(child.children);
            }
            return head;
        }


        /**
         * 将二叉树恢复成多叉树
         * @param root
         * @return
         */
        public Node decode(TreeNode root) {
            if (root == null){
                return null;
            }
            return new Node(root.val,de(root.left));
        }

        private List<Node> de (TreeNode root) {
            List<Node> list = new ArrayList<>();
            while (root != null){
                // 从左开始恢复
                Node node = new Node(root.val, de(root.left));
                list.add(node);
                root = root.right;
            }
            return list;
        }


    }
}
